PAT 1032. Sharing

#题目链接

#思路

• 既然是找相同的位置，那么相同位置后面的一定都是相同的，所以首先恢复两个链表，接着砍掉相对更长的链表的比另一个链表多出的位置，这样两个链表的长度就相同了。
• 接着就查找了，遍历 OR 二分？
• 题目中的ｉ，ａ等是没有用的

#知识点

• python中格式化打印int，用

  print "%06d"%a     #前面的0用来表示，不够6位用0补齐

  • 在C中，用

    printf("%.6d",a)    //前面的.(点)用来表示，不够6位用0补齐，默认为空格

#样例代码(c++ && python一个样例超时）
python在搜索两个链表相同位置的时候用的是从头遍历的方法，结果超时；然后改成二分查找，还是超时；最后只好用c++重写。

下面分别是python代码和C++代码

(s1,s2,n) = (int(x) for x in raw_input().split())
r=[-1]*100000
flag = False
def binary(lo,lt):
    low = 0
    high = len(lt) -1
    common = -1
    while low <=high:
        mid = (low + high)/2
        if lo[mid] == lt[mid]:
            common = lt[mid]
            high = mid -1
        else:
            low = mid + 1
    return common
for i in range(n):
    (ss1,ss2,a) = (x for x in raw_input().split())
    a = int(a)
    ss1 = int(ss1)
    r[ss1] = a
cn1=0
pos1=s1
l1=[]
while pos1 != -1:
    l1.append(pos1)
    cn1 = cn1 + 1
    pos1 = r[pos1]
cn2=0
pos2=s2
l2=[]
while pos2 != -1:
    l2.append(pos2)
    cn2 = cn2 + 1
    pos2 = r[pos2]

if len(l1) < len(l2):
    len1 = l2
    len2 = l1
else:
    len1 = l1
    len2 = l2
common = binary(len1[(len(len1)- len(len2)):],len2)
if common == -1:
    print "-1"
else:
    print "%05d"%common

C++ Sample code

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;
int binary(vector<int> a, vector<int> b)
{
    int sub = a.size() - b.size();
    int common=-1,low=0,high=b.size()-1;
    while(low <= high)
    {
        int mid = (low+high)/2;
        if(a[sub+mid] == b[mid])
            high=mid-1,common=b[mid];
        else
            low=mid+1;
    }
    return common;
}
int main()
{
    int s1,s2,n;
    //cin>>s1>>s2>>n;
    scanf("%d %d %d",&s1,&s2,&n);
    int r[100000];
    memset(r,-1,100000);
    for(int i=0;i<n;i++)
    {
        int s,e;
        char w;
        //cin>>s>>w>>e;
        scanf("%d %c %d",&s,&w,&e);
        r[s] = e;
    }
    vector<int> a,b;
    while(s1 != -1)
        a.push_back(s1),s1=r[s1];
    while(s2 != -1)
        b.push_back(s2),s2=r[s2];
    int common = -1;
    if(a.size()>b.size())
        common = binary(a,b);
    else
        common = binary(b,a);
    if(common == -1) printf("-1\n");
    else printf("%.5d\n",common);
}